package org.algorithm.熊猫.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;


/**
 * @Date 2022/2/27
 * @Link {https://leetcode-cn.com/problems/merge-k-sorted-lists/}
 */
public class 合并K个升序链表 {

    @Test
    public void test() {
        ListNode listNode1 = ListNode.build(1, 2, 3);
        ListNode listNode2 = ListNode.build(1, 2, 2);
        ListNode node = mergeKLists(new ListNode[]{listNode1, listNode2});
        System.out.println(ListNode.print(node));
    }

    /**
     * 分治解法
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * 优先队列解法
     *
     * @param lists
     * @param start
     * @param end
     * @return
     */




    //分而治之
    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (start > end) {
            return null;
        }

        int mid = (start + end) >> 1;
        return mergeTwo(merge(lists, start, mid), merge(lists, mid + 1, end));
    }

    private ListNode mergeTwo(ListNode merge, ListNode merge1) {
        if (merge == null || merge1 == null) {
            return merge != null ? merge : merge1;
        }
        //合并两个链表
        ListNode dyHead = new ListNode(0);
        ListNode tail = dyHead;
        ListNode mergeNode = merge;
        ListNode merge1Node = merge1;
        while (mergeNode != null && merge1Node != null) {
            if (mergeNode.val > merge1Node.val) {
                tail.next = merge1Node;
                merge1Node = merge1Node.next;
            } else {
                tail.next = mergeNode;
                mergeNode = mergeNode.next;
            }
            tail = tail.next;
        }
        tail.next = (mergeNode != null ? mergeNode : merge1Node);
        return dyHead.next;
    }

}
